前言(扯淡)

数论分块是莫比乌斯反演和某些数学题有时候会用到的一个玩意,也是属于那种知道就知道不知道就不知道的内容,现场推如果不知道具体形式感觉还是很难想出来的.这篇博客就尝试用肯定很不严谨的态度尝试"证明"一下相关的内容,实际上就是能在不借助其他信息的前提下能独立推出正确的结论这个目的.

数论分块

考虑求下面这个式子:

$\sum\limits_{i=1}^n \left\lfloor\frac{n}{i}\right\rfloor$

数论分块的重要依据就是$\left\lfloor\frac{n}{i}\right\rfloor$这$n$个值排成一列,呈单调下降趋势,且是一段一段的.因此可以推出每一段的左右区间各自在哪,并借助类似前缀和的想法快速求和.由于最多只有$\sqrt{n}$级别的不同的数,因此只要求和部分是$O(1)$的,整个求和部分就是$O(\sqrt{n})$的.

复杂度证明

整个序列的不同的数的个数是$\sqrt{n}$级别的
对于$i$而言,有两种取值:
①$i \leq \left\lfloor\sqrt{n} \right\rfloor$的$\left\lfloor\frac{n}{i}\right\rfloor$有$\left\lfloor\sqrt{n} \right\rfloor$种取值.

②$i > \left\lfloor\sqrt{n} \right\rfloor$的$\left\lfloor\frac{n}{i}\right\rfloor$由于$\left\lfloor\frac{n}{i}\right\rfloor \leq \left\lfloor\sqrt{n} \right\rfloor$因此也只有$\sqrt{n}$种取值.

综上,分段是$\sqrt{n}$级的.

假定现在知道区间左端点是$l$,要求右端点$r$.也就是要找到一个最大的$r$满足$\left\lfloor\frac{n}{l}\right\rfloor = \left\lfloor\frac{n}{r}\right\rfloor$.

$r$的取值结论是$r = \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor$

取值证明

证明他是正确的还是比较容易的.
首先对于这段区间而言,其中每一个值都是$\left\lfloor\frac{n}{l}\right\rfloor$

$r = \left\lfloor\frac{n}{\left\lfloor\frac{n}{l}\right\rfloor}\right\rfloor \leq \frac{n}{\left\lfloor\frac{n}{l}\right\rfloor} < r + 1$
换一下位置可以得到:
$\begin{cases}\left\lfloor\frac{n}{l}\right\rfloor \leq \frac{n}{r}\\\frac{n}{r+1} < \left\lfloor\frac{n}{l}\right\rfloor\end{cases}$
这个结论即证明了$r$就是右端点,右移一位就不满足.
对于初始的$l$来说,他肯定起始于数列的开头,之后每一次都可以往后推$r$已经更新$l$的位置.便可以解决开头的问题了.

模板代码

int f(int n)
{
    int res = 0;
    for(int l = 1,r;l <= n;l = r + 1)
    {
        r = n / (n / l);
        res += (r - l + 1) * (n / l);
    }
    return res;
}

例题① [CQOI2007]余数求和

原题链接:luogu 2261
题目大意:
给定$n,k$,计算:

$G(n,k) = \sum\limits_{i=1}^n k\%i$

思路

考虑变换形式:对于$k \% i$来说,他等价于$k - \left\lfloor\frac{k}{i}\right\rfloor * i$
进一步,原式$= \sum\limits_{i=1}^n{k - \left\lfloor\frac{k}{i}\right\rfloor * i}$其中$k$是个常数,可以拿出来,因此继续化简得到$n*k - \sum\limits_{i=1}^n{\left\lfloor\frac{k}{i}\right\rfloor * i}$.距离数列分块的形式还多了一个$i$,对于求和的每一个单独的元素来说,$i$就是一段等差数列求和的值.对于$[l,r]$这段区间,$i$部分产生的贡献即$(l +r) * (r - l + 1) / 2$再加上数论分块的部分即可.

代码

typedef long long ll;
#define int ll
int n,k;
int f(int n)
{
    int res = 0;
    for(int l = 1,r;l <= n;l = r + 1)
    {
		r = k / l ? min(k / (k / l),n) : n;
        res += (k / l) * (r + l) * (r - l + 1) / 2;
    }
    return res;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	int fres = f(n);
    printf("%lld",n * k - fres);
    return 0;
}